/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author uv
 */
public class Executer {

    public static void main(String[] args) {
        Problems euler = new Problems();
        /*
         * 
         
        System.out.println(op(1) + euler.problem1());
        System.out.println(op(2) + euler.problem2());
        System.out.println(op(3) + euler.problem3());
        System.out.println(op(4) + euler.problem4());
        System.out.println(op(5) + euler.problem5());
        System.out.println(op(6) + euler.problem6());
        System.out.println(op(7) + euler.problem7());
        System.out.println(op(8) + euler.problem8());
        System.out.println(op(9) + euler.problem9());
        System.out.println(op(10) + euler.problem10());
         * 
         */
        System.out.println(op(11) + euler.problem11());
    }

    public static String op(int prob) {
        return "Problem " + prob + " solution: ";
    }
}

class Problems {

    /**
     * Find the greatest common divisor of two long numbers
     * @param a
     * @param b
     * @return 
     */
    private static long gcd(long a, long b) {
        while (b > 0) {
            long temp = b;
            b = a % b; // % is remainder
            a = temp;
        }
        return a;
    }

    /**
     * Find the least common multiple of two long numbers
     * @param a
     * @param b
     * @return 
     * 
     */
    private static long lcm(long a, long b) {
        return a * (b / gcd(a, b));
    }

    public String revString(String str) {
        char[] pal = new char[str.length()];
        pal = str.toCharArray();
        for (int i = 0; i < (str.length() / 2); i++) {
            char tmp = pal[i];
            pal[i] = pal[(pal.length - 1) - i];
            pal[(pal.length - 1) - i] = tmp;
        }
        return new String(pal);
    }

    public boolean isPrime(int num) {
        /*
         * This is a simple brute force prime number finder.
         * It checks every integer up to num to see if it divides evenly.
         * If it doesn't, then num is a prime
         * 
         */

        boolean isprime = true;
        for (int i = 2; i <= (Math.sqrt(num)); i++) {     // Only need to check as far as sqrt(num)
            if ((num % i) == 0) // Divides evenly
            {
                isprime = false;
            }
        }
        return (num != 1) ? isprime : false;  // Check the corner case of 1.
    }

    public int problem1() {
        /*
         * If we list all the natural numbers below 10 that are multiples of 3 or 5,
         * we get 3, 5, 6 and 9. The sum of these multiples is 23.
         * Find the sum of all the multiples of 3 or 5 below 1000.
         */


        int sum = 0;             // The running sum of values that meet the problem critera
        int upperBounds = 1000;  // The highest value were checking numbers by.
        // Set this to 10 to verify that the solution is 23.

        for (int i = 1; i < upperBounds; i++) {

            // If the remainder of a number between 1 and the upper bounds of the problem
            // is 0 when divided by 3 or by 5.
            if (((i % 3) == 0) || ((i % 5) == 0)) {
                // Then add all those numbers together.
                sum += i;
            }
        }

        // Output the result
        return sum;

    }

    public int problem2() {
        /*
         * Each new term in the Fibonacci sequence is generated by 
         * adding the previous two terms. By starting with 1 and 2,
         * the first 10 terms will be:
         * 
         * 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
         * 
         * By considering the terms in the Fibonacci sequence whose
         * values do not exceed four million, find the sum of the 
         * even-valued terms.
         */
        int upperBound = 4000000;   // Max value to check criteria under
        int sum = 0;                // variable to hold the sum meeting the criteria
        int num1 = 1;               // num1 and num2 are two adjacent running fibonacci numbers
        int num2 = 2;
        int fib = num2;             // Begin checking the first even value.

        // Generate fibonacci numbers up to the upper bounds of the problem
        while (num2 < upperBound) {
            /* Some ternary operator fun:
             * If the fibonacci number is even "((fib % 2)==0)"
             * Then sum = sum + fib.
             * Else sum = sum             */
            sum = ((fib % 2) == 0) ? (sum + fib) : sum;
            fib = num1 + num2;        // Generate the next fibonacci number
            num1 = num2;            // Set the respective running values and continue
            num2 = fib;
        }
        return sum;                 // Return the results
    }

    public int problem3() {
        /*
         * The prime factors of 13195 are 5, 7, 13 and 29.
         * 
         * What is the largest prime factor of the number 600851475143 ?
         */
        long upperBounds = 600851475143L;
        int maxPrime = 1;
        long maxIterator = upperBounds;
        for (int i = 1; i < maxIterator; i += 2) {
            maxIterator = upperBounds / i;
            if (isPrime(i)) {
                if (upperBounds % i == 0) {
                    System.out.println(i);
                    maxPrime = i;
                }
            }
        }
        return maxPrime;
    }

    public int problem4() {
        /*
         * A palindromic number reads the same both ways. The largest palindrome 
         * made from the product of two 2-digit numbers is 9009 = 91  99.
         * Find the largest palindrome made from the product of two 3-digit numbers.
         * 
         */
        int largePal = 0;
        /*
         * Create two nested loops to generate every product of 3 digit numbers
         */
        for (int i = 100; i <= 999; i++) {
            for (int j = 100; j <= 999; j++) {
                int product = i * j; // 3 digit numbers products
                /*
                 * Convert the int to string/char array for easier manipulation.
                 * Then do an initial palindrome check to reduce run time.
                 * Then do a final palindrome check to finalize. 
                 */
                String str = new Integer(product).toString();
                if (str.charAt(0) == str.charAt(str.length() - 1)) {
                    String str2 = revString(str);  // reverse the string
                    if (str.equalsIgnoreCase(str2)) { // is palindrome?
                        if (product > largePal) {
                            largePal = product;
                        }
                    }
                }
            }
        }

        return largePal;

    }

    /**
     * Reverses a string
     * 
     * @param str string that gets reversed.
     * @return    reversed string.
     * 
     */
    /**
     * Project Euler problem number 5
     * 
     * 2520 is the smallest number that can be divided 
     * by each of the numbers from 1 to 10 without any remainder.
     * 
     * What is the smallest positive number that is evenly 
     * divisible by all of the numbers from 1 to 20?
     * 
     * @return long - The solution to the description
     */
    public long problem5() {
        long result = 1;
        for (int i = 1; i <= 20; i++) {
            result = lcm(i, result);
        }
        return result;
    }

    public int problem6() {
        int pos = 0;
        int sop = 0;
        for (int i = 1; i <= 100; i++) {
            sop += i * i;
            pos += i;
        }
        pos *= pos;
        return pos - sop;
    }

    public int problem7() {
        int primeCounter = 1;
        int prime = 1;
        while (primeCounter <= 10001) {
            prime++;
            if (isPrime(prime)) {
                primeCounter++;
            }

        }
        return prime;

        //return result;
    }

    /**
     * Find the greatest product of five consecutive digits in the 1000-digit number.
     * 
     * @return integer - Solution to problem
     */
    public int problem8() {
        String bigNum = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
        int strLength = bigNum.length() - 1;
        int maxProd = 0;
        for (int i = 0; i <= strLength - 5; i++) {
            char[] sub = (bigNum.substring(i, i + 5)).toCharArray();
            int prod = 1;
            for (int j = 0; j < 5; j++) {
                prod *= Character.getNumericValue(sub[j]);
            }
            if (prod > maxProd) {
                maxProd = prod;
            }
        }
        return maxProd;
    }

    /**
     * A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
     * a^2 + b^2 = c^2
     * 
     * For example, 32 + 42 = 9 + 16 = 25 = 52.
     * 
     * There exists exactly one Pythagorean triplet for which a + b + c = 1000.
     * Find the product abc.
     * 
     * @return - int, solution
     */
    public int problem9() {
        int sum = 1000;
        for (int a = 1; a < 1000; a++) {
            for (int b = 1; b < 1000 - a; b++) {
                int c = sum - (a + b);
                if (a * a + b * b == c * c) {
                    return a * b * c;
                }
            }
        }
        return 0;
    }

    /**
     * Project Euler - Problem 8
     * 
     * The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
     * Find the sum of all the primes below two million.
    
     * @return int - the solution
     */
    public long problem10() {
        int max = 2000000;
        long sum = 0;
        for (int i = 2; i <= max; i++) {
            if (isPrime(i)) {
                sum += i;
            }
        }

        return sum;
    }

    public int problem11() {
        int[][] numArr = new int[][]{
            {8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8},
            {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0},
            {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65},
            {52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91},
            {22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
            {24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
            {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
            {67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21},
            {24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
            {21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95},
            {78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92},
            {16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57},
            {86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
            {19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40},
            {4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
            {88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
            {4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36},
            {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16},
            {20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54},
            {1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48}};
        int width = numArr.length-1;
        int horizProd = 0; int vertProd = 0; int diagProd1 = 0; int diagProd2 = 0;
        int horizProdMax = 0; int vertProdMax = 0; int diagProdMax = 0;
        for(int row = 0;row<=width;row++) {
            for(int col = 0;col<=width-4;col++) {
                horizProd = numArr[row][col]*numArr[row][col+1]*numArr[row][col+2]*numArr[row][col+3];
                if (horizProd>horizProdMax) horizProdMax = horizProd;
            }
        }
        for(int col = 0;col<=width;col++) {
            for(int row = 0;row<=width-4;row++) {
                vertProd = numArr[row][col]*numArr[row+1][col]*numArr[row+2][col]*numArr[row+3][col];
                if (vertProd>vertProdMax) vertProdMax = vertProd;
            }
        }
        for(int col = 0;col<=width-4;col++) {
            for(int row = 0;row<=width-4;row++) {
                diagProd1 = numArr[row][col]*numArr[row+1][col+1]*numArr[row+2][col+2]*numArr[row+3][col+3];
                diagProd2 = numArr[row+3][col]*numArr[row+2][col+1]*numArr[row+1][col+2]*numArr[row][col+3];
                diagProdMax = (diagProd1 > diagProd2) ? (diagProd1>diagProdMax) ? diagProd1 : diagProdMax : (diagProd2 > diagProdMax) ? diagProd2 : diagProdMax;
            }
        }

        return (diagProdMax>vertProdMax) ? (diagProdMax > horizProdMax) ? diagProdMax : horizProdMax : vertProdMax;
        
    }
}
